﻿#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
//剑指 Offer II 066. 单词之和❤️
//struct Trix
//{
//	vector<Trix*> _children;
//	int _val;
//	Trix()
//		:_val(0)
//		, _children(26, nullptr)
//	{}
//};
//class MapSum {
//public:
//	/** Initialize your data structure here. */
//	MapSum()
//	{
//		root = new Trix();
//	}
//
//	void insert(string key, int val)
//	{
//		int delval = val;//key可能存在或者不存在，用来加等或者减等
//		//已经有键值对就替换成新的键值对
//		if (hash.count(key))
//		{
//			delval -= hash[key];
//		}
//		//注意不能将它放到if上面
//		Trix* node = root;
//		hash[key] = val;
//		for (auto c : key)
//		{
//			if (node->_children[c - 'a'] == nullptr)
//			{
//				node->_children[c - 'a'] = new Trix();
//			}
//			node = node->_children[c - 'a'];
//			node->_val += delval;
//		}
//	}
//
//	int sum(string prefix) {
//		Trix* node = root;
//		for (auto c : prefix)
//		{
//			if (node->_children[c - 'a'] == nullptr)
//			{
//				return 0;
//			}
//			else
//			{
//				node = node->_children[c - 'a'];
//			}
//		}
//		return node->_val;
//	}
//private:
//	unordered_map<string, int> hash;
//	Trix* root;
//};

//剑指 Offer II 067. 最大的异或❤️
//struct Trix
//{
//	Trix* left;//代表0
//	Trix* right;//代表1;
//	Trix()
//		:left(nullptr)
//		, right(nullptr)
//	{}
//};
//class Solution {
//public:
//
//	void add(int nums)
//	{
//		Trix* node = root;
//		for (int k = 30; k >= 0; k--)
//		{
//			int bit = nums >> k & 1;
//			if (bit == 0)
//			{
//				if (!node->left)
//				{
//					node->left = new Trix();
//				}
//				node = node->left;
//			}
//			else
//			{
//				if (!node->right)
//				{
//					node->right = new Trix();
//				}
//				node = node->right;
//			}
//		}
//	}
//	int check(int nums)
//	{
//		Trix* node = root;
//		int res = 0;
//		for (int k = 30; k >= 0; k--)
//		{
//			int bit = nums >> k & 1;
//			if (bit == 0)
//			{
//				if (node->right != nullptr)
//				{
//					node = node->right;
//					res = res * 2 + 1;
//				}
//				else
//				{
//					node = node->left;
//					res = res * 2;
//				}
//			}
//			else
//			{
//				if (node->left != nullptr)
//				{
//					node = node->left;
//					res = res * 2 + 1;
//				}
//				else
//				{
//					node = node->right;
//					res = res * 2;
//				}
//			}
//		}
//		return res;
//	}
//	int findMaximumXOR(vector<int>& nums) {
//		int n = nums.size();
//		int res = 0;
//		for (int i = 1; i < n; i++)
//		{
//			//先添加后查询
//			add(nums[i - 1]);
//			res = max(res, check(nums[i]));
//		}
//		return res;
//	}
//private:
//	Trix* root = new Trix();
//};